package leetcode_700;

/**
 *@author 周杨
 *KnightProbabilityInChessboard_688 骑士走n步  能最终能停留在棋盘上的概率
 *describe:用动态规划加上深度搜索 AC 13%
 *2018年10月8日 上午11:52:53
 */
public class KnightProbabilityInChessboard_688 {
	public static void main(String[] args) {
		System.out.println(4d/64d);
		System.out.println(Math.pow(8d, 2));
	}
	int i=0;
	int dp[][][];
	/**
	 * describe:题目可能没有看懂 不知道哪里出了问题  可能不能用次数来计算
	 * 2018年10月8日 上午11:51:45
	 */
	public double knightProbability(int N, int K, int r, int c) {
		this.dp=new int[K+1][N][N];
        help(N,K,r,c);
        System.out.println(i);
        return dp[K][r][c]/(Math.pow(8, K));
    }
	
	public int help(int n,int time,int row,int col) {
		if(row<0||row>=n||col<0||col>=n) {//已经越界
			return 0;
		}
		if(dp[time][row][col]!=0)
			return dp[time][row][col];
		if(time==0) {
			++i;
			dp[time][row][col]=1;
			return 1;
		}
		int res=0;
		res+=help(n,time-1,row+2,col+1);
		res+=help(n,time-1,row+2,col-1);
		res+=help(n,time-1,row-2,col+1);
		res+=help(n,time-1,row-2,col-1);
		res+=help(n,time-1,row+1,col+2);
		res+=help(n,time-1,row+1,col-2);
		res+=help(n,time-1,row-1,col+2);
		res+=help(n,time-1,row-1,col-2);
		dp[time][row][col]=res;
		return res;
	}
	
	 private int[][] dirs = new int[][]{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
	    /**
	     * describe:我是用的步数计算最终结果 这里直接叠加概率
	     * 2018年10月8日 上午11:53:38
		 */
	    public double knightProbability1(int N, int K, int r, int c) {
	        double[][][] dp = new double[K + 1][N][N];
	        dp[0][r][c] = 1;
	        for (int step = 1; step <= K; step++) {
	            for (int i = 0; i < N; i++) {
	                for (int j = 0; j < N; j++) {
	                    for (int[] dir : dirs) {
	                        int x = dir[0] + i;
	                        int y = dir[1] + j;
	                        if (x < 0 || x >= N || y < 0 || y >= N) continue;
	                        dp[step][i][j] += dp[step - 1][x][y] * 0.125;
	                    }
	                }
	            }
	        }
	        double res = 0;
	        for (int i = 0; i < N; i++) {
	            for (int j = 0; j < N; j++) {
	                res += dp[K][i][j];
	            }
	        }
	        return res;
	    }
}
